﻿
//本文件用于记录博客:动态规划--股票买卖问题的用例以及代码
//博客链接:https://blog.csdn.net/weixin_64099089/article/details/147312684?spm=1001.2014.3001.5501


//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

//122. 买卖股票的最佳时机 II
//给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
//
//在每一天，你可以决定是否购买和 / 或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
//
//返回 你能获得的 最大 利润 。
//
//
//
//示例 1：
//
//输入：prices = [7, 1, 5, 3, 6, 4]
//输出：7
//解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
//随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
//最大总利润为 4 + 3 = 7 。
//示例 2：
//
//输入：prices = [1, 2, 3, 4, 5]
//输出：4
//解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
//最大总利润为 4 。
//示例 3：
//
//输入：prices = [7, 6, 4, 3, 1]
//输出：0
//解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。
//
//
//提示：
//
//1 <= prices.length <= 3 * 104
//0 <= prices[i] <= 104

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        //f[i] 表示第i天结束时，处于买入状态时的最大利润
        //g[i] 表示第i天结束时，处于可买入状态时的最大利润
        vector<int>f(n + 1), g(n + 1);
        f[0] = INT_MIN, g[0] = 0;
        for (int i = 1; i <= n; ++i) {
            f[i] = max(f[i - 1], g[i - 1] - prices[i - 1]);
            g[i] = max(g[i - 1], f[i - 1] + prices[i - 1]);
        }
        return g[n];
    }
};




//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
//
//309. 买卖股票的最佳时机含冷冻期
//给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​
//
//设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票） :
//
//卖出股票后，你无法在第二天买入股票(即冷冻期为 1 天)。
//注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
//
//
//示例 1:
//
//输入: prices = [1, 2, 3, 0, 2]
//输出 : 3
//解释 : 对应的交易状态为 : [买入, 卖出, 冷冻期, 买入, 卖出]
//	示例 2 :
//
//		输入 : prices = [1]
//		输出 : 0
//
//
//		提示：
//
//		1 <= prices.length <= 5000
//		0 <= prices[i] <= 1000

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(3, vector<int>(n));
        dp[0][0] = -prices[0], dp[1][0] = dp[2][0] = 0;
        for (int i = 1; i < n; ++i) {
            dp[0][i] = max(dp[0][i - 1], dp[2][i - 1] - prices[i]);
            dp[1][i] = dp[0][i - 1] + prices[i];
            dp[2][i] = max(dp[2][i - 1], dp[1][i - 1]);
        }
        return max(dp[1][n - 1], dp[2][n - 1]);
    }
};


//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
//
// 
// 714. 买卖股票的最佳时机含手续费
//给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
//
//你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
//
//返回获得利润的最大值。
//
//注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
//示例 1：
//
//输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
//输出：8
//解释：能够达到的最大利润 :
//在此处买入 prices[0] = 1
//在此处卖出 prices[3] = 8
//在此处买入 prices[4] = 4
//在此处卖出 prices[5] = 9
//总利润 : ((8 - 1) - 2) + ((9 - 4) - 2) = 8
//示例 2：
//
//输入：prices = [1, 3, 7, 5, 10, 3], fee = 3
//输出：6
//
//
//提示：
//
//1 <= prices.length <= 5 * 104
//1 <= prices[i] < 5 * 104
//    0 <= fee < 5 * 104

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<int> f(n + 1), g(n + 1);
        f[0] = -0x3fffffff;
        for (int i = 1; i <= n; ++i) {
            f[i] = max(f[i - 1], g[i - 1] - prices[i - 1]);
            g[i] = max(g[i - 1], f[i - 1] + prices[i - 1] - fee);
        }
        return g[n];
    }
};


//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
//123. 买卖股票的最佳时机 III
//给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
//
//设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
//
//注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
//
//示例 1:
//
//输入：prices = [3, 3, 5, 0, 0, 3, 1, 4]
//输出：6
//解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3 - 0 = 3 。
//随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4 - 1 = 3 。
//示例 2：
//
//输入：prices = [1, 2, 3, 4, 5]
//输出：4
//解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
//注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
//因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
//示例 3：
//
//输入：prices = [7, 6, 4, 3, 1]
//输出：0
//解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
//示例 4：
//
//输入：prices = [1]
//输出：0
//
//
//提示：
//
//1 <= prices.length <= 105
//0 <= prices[i] <= 105


class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(2, vector<int>(n + 1)), g(2, vector<int>(n + 1));
        // f[0][0] = f[1][0] = -prices[0];
        f[0][0] = f[1][0] = -0x3fffffff;
        for (int i = 1; i <= n; ++i) {
            f[0][i] = max(-prices[i - 1], f[0][i - 1]);
            f[1][i] = max(f[1][i - 1], g[0][i - 1] - prices[i - 1]);
            g[0][i] = max(g[0][i - 1], f[0][i - 1] + prices[i - 1]);
            g[1][i] = max(g[1][i - 1], f[1][i - 1] + prices[i - 1]);
        }
        return max(0, max(g[0][n], g[1][n]));
    }
};


//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
//
//188. 买卖股票的最佳时机 IV
//给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
//
//设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
//
//注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
//
//
//
//示例 1：
//
//输入：k = 2, prices = [2, 4, 1]
//输出：2
//解释：在第 1 天(股票价格 = 2) 的时候买入，在第 2 天(股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4 - 2 = 2 。
//示例 2：
//
//输入：k = 2, prices = [3, 2, 6, 5, 0, 3]
//输出：7
//解释：在第 2 天(股票价格 = 2) 的时候买入，在第 3 天(股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6 - 2 = 4 。
//随后，在第 5 天(股票价格 = 0) 的时候买入，在第 6 天(股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3 - 0 = 3 。
//
//
//提示：
//
//1 <= k <= 100
//1 <= prices.length <= 1000
//0 <= prices[i] <= 1000

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        //f[i][j] 表示第 i 天结束时，处于第 j 轮交易的买入状态时，最大利润
        //g[i][j] 表示第 i 天结束时，处于第 j 轮交易的卖出状态时，最大利润
        int n = prices.size();
        if (n <= 1)return 0;
        k = min(k, n / 2); //最多完成 n/2笔交易
        vector<vector<int>> f(n, vector<int>(k));
        auto g = f;
        //初始化f表
        int minprice = prices[0];
        // j = 0表示第i天结束时，处于第 1 轮交易的买入状态的最大利润 
        for (int i = 0; i < n; ++i) {
            minprice = min(minprice, prices[i]);
            f[i][0] = -minprice;
        }
        // i = 0 表示第 i 天结束时，处于第 j 轮交易的买入状态的最大利润
        for (int j = 1; j < k; ++j) {
            f[0][j] = -prices[0];
        }
        //初始化 g 表

        // i = 0 时表示第0天结束时，处于第 j 轮交易的卖出状态的最大利润，为了不影响填g[1][j]和f[1][j]，我们填无穷小
        for (int j = 0; j < k; ++j) g[0][j] = -0x3fffffff;
        //j = 0 时表示第 i 天结束时，处于第一轮状态的卖出状态的最大利润
        if (n > 1) {
            minprice = prices[0];
            for (int i = 1; i < n; ++i) {
                g[i][0] = max(prices[i] - minprice, g[i - 1][0]);
                minprice = min(minprice, prices[i]);
            }
        }
        //填表
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < k; ++j) {
                f[i][j] = max(f[i - 1][j], g[i - 1][j - 1] - prices[i]);
                g[i][j] = max(g[i - 1][j], f[i - 1][j] + prices[i]);
            }
        }
        //返回值
        int res = 0;
        for (int j = 0; j < k; ++j)res = max(res, g[n - 1][j]);
        return max(res, 0);
    }

};